\documentclass[10pt,a4paper,oneside]{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{mathtools}
\usepackage[utf8]{inputenc}
\usepackage{fullpage}

%\usepackage{pst-all}

\usepackage{multicol}
\usepackage{multirow}
\usepackage{subfigure}

\usepackage{graphicx}

\usepackage{xcolor}
\definecolor{lbcolor}{rgb}{0.95,0.95,0.95}
\definecolor{cblue}{rgb}{0.,0.0,0.6}

\usepackage[colorlinks=true]{hyperref}
\usepackage{filecontents,listings}
\lstset{language=c++,showspaces=false,showstringspaces=false,captionpos=t,literate={>>}{\ensuremath{>>}}1}
%\lstset{float}
\lstset{basicstyle=\small\ttfamily}
\lstset{lineskip=-2pt}
\lstset{keywordstyle=\color{red}\bfseries}
%\lstset{keywordstyle=\mdseries\color{red}}
\lstset{emph={inline},emphstyle=\color{red}\bfseries}
%\lstset{stringstyle=\ttfamily}
\lstset{commentstyle=\ttfamily\color{cblue}}
\lstset{backgroundcolor=\color{lbcolor},rulecolor=}
%\lstset{numbers=left}
%\lstset{numbers={none}}
%\lstset{numberstyle=\tiny}
%\lstset{numbersep=1pt}
\lstset{frame=single,framerule=0.5pt}
\lstset{belowskip=\smallskipamount}
\lstset{aboveskip=\smallskipamount}

%%%%%%%DESSIN%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{tikz}
\usetikzlibrary{shapes,arrows}

%%%%%%ALGORITME%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{algorithm,algorithmic}
%%% francisation des algorithmes
\renewcommand{\algorithmicrequire} {\textbf{\textsc{Entrées:}}}
\renewcommand{\algorithmicensure}  {\textbf{\textsc{Sorties:}}}
\renewcommand{\algorithmicwhile}   {\textbf{tantque}}
\renewcommand{\algorithmicdo}      {\textbf{faire}}
\renewcommand{\algorithmicendwhile}{\textbf{fin tantque}}
\renewcommand{\algorithmicend}     {\textbf{fin}}
\renewcommand{\algorithmicif}      {\textbf{si}}
\renewcommand{\algorithmicendif}   {\textbf{finsi}}
\renewcommand{\algorithmicelse}    {\textbf{sinon}}
\renewcommand{\algorithmicthen}    {\textbf{alors}}
\renewcommand{\algorithmicfor}     {\textbf{pour}}
\renewcommand{\algorithmicforall}  {\textbf{pour tout}}
\renewcommand{\algorithmicdo}      {\textbf{faire}}
\renewcommand{\algorithmicendfor}  {\textbf{fin pour}}
\renewcommand{\algorithmicloop}    {\textbf{boucler}}
\renewcommand{\algorithmicendloop} {\textbf{fin boucle}}
\renewcommand{\algorithmicrepeat}  {\textbf{répéter}}
\renewcommand{\algorithmicuntil}   {\textbf{jusqu'à}}

\floatname{algorithm}{Algorithme}

\let\mylistof\listof
\renewcommand\listof[2]{\mylistof{algorithm}{Liste des algorithmes}}

% pour palier au problème de niveau des algos
\makeatletter
\providecommand*{\toclevel@algorithm}{0}
\makeatother

%\listofalgorithms % pour lister les algos (après la toc)


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\graphicspath{%
   {./../../Figures/pdfs/chabanne/}%
   {./../../Figures/epss/chabanne/}%
   {./figures/}
}

\begin{document}

\section{Introduction}


\section{Interpolation}
Dans de nombreux problèmes, il est nécessaire de pouvoir interpoler une fonction définie 
sur un maillage $\Omega_{1}$ sur un autre maillage $\Omega_{2}$. 
C'est le cas par exemple de l'intéraction fluide structure, des méthodes de décomposition de domaine, 
de la méthode FBM, etc. Nous allons commencer par nous donné deux maillages :

\paragraph{}
\begin{figure}[H]
\centering
\subfigure{
\includegraphics[scale=0.35]{mesh}
} 
%\label{fig:simu}
\subfigure{
\includegraphics[scale=0.35]{spline} 
}
\caption[text1]{Maillages Simplex Bi-dimensionnelle}
\end{figure}
%Figure des maillages

\paragraph{}
Soient :
\begin{itemize}
\item $\Omega_{1}$
\item $\Gamma$
\end{itemize}

\subsection{Approximation par éléments finis et spectraux}
\paragraph{}
Dans le cadre des méthodes des éléments finis et spectrales, nous avons besoins de définir
un élément spectraux comme étant le triplet (K, $\Sigma$, $\mathbb{P}_{k}$ ), avec :
\begin{itemize}
\item $K\in \mathbb{R}^{d}$ un élément géométrique compacte et connexe et 
d'intérieur non vide ( $\overset{\circ}{A} \neq \varnothing  $ ) %emptyset  %varnothing 
%\item $\Sigma$ un ensemble de point( ou degré de liberté) distinct et appartenant à K; $\Sigma = \left\{ a_{1},...,a_{N}\right\}$
\item $\mathbb{P}_{k}$ un espace vectoriel, de dimension finie de fonctions réelles (ou vectorielles) définies sur $K$
\item $\Sigma$ un ensemble de $N$ forme linéaire $\sigma_{x_{i}}$ définies sur $\mathbb{P}_{k}$
\end{itemize}

Par exemple les éléments finis $P_{3}$ de Lagrange définit sur un triangle d'ordre 2
\begin{eqnarray}
\sigma_{x_{i}} :\mathbb{P}_{k} &\longrightarrow &\mathbb{R} \\
 p &\longmapsto &p\left(x_{i}\right)
\end{eqnarray}
Avec les $x_{i}$ un ensemble de point d'interpolation.( par exemple : Warp Blend, Fekete, ...)


\paragraph{}
Nous donnons ensuite un espace d'approximation $X_{h}$ de dimension fini, défini classiquement par :
\begin{equation}
X_{h} = \left\{ v_{h} \in C^{0}\left( \bar{\Omega}\right)  \mid v_{h\mid K} \in \mathbb{P}_{k}, \forall K \in \tau\right\}
\end{equation}
Cet espace est un sous espace de $H^{1}\left(\Omega\right)$, continue sur l'ensemble du domaine $\Omega$ et
polynomial par morceau sur chaque element $K$ du maillage $\mathcal{T}_{h}$


\paragraph{}
Soit une fonction $v \in X_{h}$ 
qui a pu être construite par divers projetion (A DETAILLER).

\paragraph{}
Nous pouvons maintenant définir notre opérateur d'interpolation comme étant

\begin{eqnarray}
\pi : X_{h} &\longrightarrow  &\mathbb{R}^{q} \\
v &\longmapsto  &\pi(v) = \sum_{i=0}^{N_{dof}} v\left(x_{i}\right) \Phi_{i} 
\end{eqnarray}

Cette opérateur d'interpolation est un opérateur global, nous introduisons alors 
l'opérateur d'interpolation local, construit de manière similaire mais 
utilisable localement sur un élément $K \in \tau_{h}$ :
\begin{equation}
\pi_{K}(v) = \sum_{i=0}^{N_{dof}} v\left(x_{i}\right) \Phi_{i} \mid_{K} 
\hspace{1cm} \forall v \in X_{h}
\end{equation}

\subsection{Transformation géométrique}
\paragraph{}
Les deux opérateurs d'interpolation définis précédemment requiert la connaissance des fonctions
de base globales $\Phi_{i}$ sur chaque élément $K$. Mais en pratique celle ci ne sont pas
calculé explicitement sur chaque élément, leurs nombre et donc leurs cout étant très important.
On préfère alors calculé les fonctions de base locales sur un élément de référence $\hat{K}$
et grâce à une transformation géométrique, nous pouvons en déduire leurs évaluations.
Tout d'abord, commençons par exprimer les $\Phi_{i}\mid_{K}$ à l'aide des fonctions de base 
locales $\Phi_{j}^{k}$, associé à l'élément $K$ :
\begin{equation}
\phi_{i}\mid_{K}\left(x\right) = \sum_{j=1}^{N_{ldof}^{K}} \Phi_{j}^{K} \left(x\right)
\ \ \ \ \ \ \ \
\forall x \in K
\end{equation}


\paragraph{}
DESCRIPTION ALGEBRIQUE ...

\paragraph{}
Nous notons par $\hat{\Phi}_{i}, i=1,N_{ldof}$ les fonctions de bases associées à l'éléments de référence et
$\varphi_{K}$ la transformation géometrique qui permet de passer de l'élément $\hat{K}$ vers l'élément $K$.
Cette transformation vérifie : (DETAILLER UN PEU)



\paragraph{}
En posant :
\begin{equation}
\hat{x} = \varphi^{-1}_{K}\left(x\right)
\ \ \ \ \text{et} \ \ \ \
\hat{\Phi}\left(\hat{x}\right) = \Phi_{K} \circ \varphi_{k}\left(\hat{x}\right)
\end{equation}
nous pouvons écrire :
\begin{equation}
\Phi_{i}\left(x\right) = \Phi_{i} \circ \varphi \circ \varphi^{-1} \left(x\right)
= \Phi \circ \varphi \left( \hat{x} \right) = \hat{\Phi} \left( \hat{x} \right)
\end{equation}

D'où :

\begin{equation}
\pi_{K}(v)(x) = \sum_{i=1}^{N} v\left(a_{i}\right) \hat{\Phi}_{i} \left( \hat{x} \right)
\ \ \ \ \forall x \in K
\end{equation}


\subsection{Interpolation des fonctions de base}

\begin{eqnarray}
\int_{\Omega_{2}} u_{1}
&=& \sum_{K\in\Omega_{2}} \int_{K} \pi_{K} \left(u_{1}\right) \\
&=& \sum_{K\in\Omega_{2}} \int_{K} \sum_{j=1}^{N_{ldof}} u_{1}\left(\varphi\left(\hat{a_{j}}\right)\right) \hat{\Phi}_{j} \\
&=& \sum_{K\in\Omega_{2}} \sum_{q=1}^{N_{q}} \sum_{j=1}^{N_{ldof}}
u_{1}\left(\varphi\left(\hat{a_{j}}\right)\right) \hat{\Phi}_{j}\left(x_{p}\right)
\end{eqnarray}

\paragraph{}
METTRE LES ALGOS ....

\subsection{Extrapolation des fonctions de base}

FIGURE MONTRANT LE PROBLEME

\subsection{Opérateur d'interpolation}
Nous souhaitons maintenant pouvoir interpoler un champ sur un maillage différent
ou simplement sur un espace de fonction différent(le maillage pouvant être identique).

\paragraph{}
Soit $\Omega_{1}$(resp $\Omega_{2}$) un maillage et $X_{h}$(resp $Y_{h}$) un espace de fonction
associé à $\Omega_{1}$(resp $\Omega_{2}$). Nous disposons d'une fonction $u \in X_{h}$ et
on cherche à évaluer $u$ en un point $x_{i} \in \Omega_{2}$.

\begin{equation}
u\left(x\right) = \sum_{K} \sum_{j=1}^{N_{ldof}} u\left((a_{i}\right) \Phi_{j}\left(x\right)
\end{equation}


\begin{equation}
\pi : X_{h} \longrightarrow Y_{h}
\end{equation}

\section{kdtree}
La méthode kdtree est une méthode basée sur le partitionnement de données. 
Elle permet d'organiser les points d'un espace de dimension $k$ pour en
accélerer leur traitement comme la recherche des points les plus proches.
La structure de données est représenté sous la forme d'un arbre binaire
dans lequel chaque nœud contient un point en dimension k.
Chaque nœud non terminal divise l'espace en deux demi-espaces. 
Les points situés dans chacun des deux demi-espaces sont stockés 
dans les branches gauche et droite du nœud courant. Par exemple, si un nœud 
donné divise l'espace selon un plan normal à la direction (Ox), tous les points 
de coordonnée x inférieure à la coordonnée du point associé au nœud seront stockés
dans la branche gauche du nœud. De manière similaire, les points de coordonnée x 
supérieure à celle du point considéré seront stockés dans la branche droite du nœud.

\begin{figure}[h]
\begin{center}
\subfigure[Organisation des points de l'espace] {
\begin{tikzpicture}[scale=1]
%\draw [->,gray!100,dashed] (-0.4,0) -- (1.7,0);
%\draw (1.7,0.0) node[below] {$\hat{x}$};
%\draw [->,gray!100,dashed] (0,-0.4) -- (0,1.7);
%\draw (0,1.7) node[left] {$\hat{y}$};
%\draw[black] (0.0,0.0) -- (1.0,0) -- (0.0,1.0) -- (0.0,0.0);

\draw[-,gray!100,dashed] (-0.7,3) -- (-0.7,-3);
%draw[-,gray!100,dashed] (-4,-0.5) -- (0,-0.5);
\draw[-,gray!100,dashed] (-0.7,1) -- (3,1);
\draw[-,gray!100,dashed] (-5,-0.5) -- (-0.7,-0.5);

%\draw[-,gray!100,dashed] (-1.7,-0.5) -- (-1.7,3);



\draw (0.7,1) node {$\bullet$} ;
\draw (0.7,1) node[above] {$\left(0.7,1 \right)$} ;
\draw (2,3) node {$\bullet$} ;
\draw (2,3) node[below] {$\left(2,3 \right)$} ;
\draw (-3,-1) node {$\bullet$} ;
\draw (-3,-1) node[left] {$\left(-3,-1 \right)$} ;
\draw (2,-2) node {$\bullet$};
\draw (2,-2) node[below] {$\left(2,-2 \right)$} ;
\draw (1.5,0) node {$\bullet$};
\draw (1.5,0) node[below] {$\left(1.5,0 \right)$} ;
\draw (-3,1.5) node {$\bullet$};
\draw (-3,1.5) node[left] {$\left(-3,1.5 \right)$} ;
\draw (-1.7,0.8) node {$\bullet$};
\draw (-1.7,0.8) node[left] {$\left(-1.7,0.8 \right)$} ;
\draw (-0.7,2) node {$\bullet$};
\draw (-0.7,2) node[above right] {$\left(-0.7,2 \right)$} ;
\draw (-1,-0.5) node {$\bullet$};
\draw (-1,-0.5) node[above left] {$\left(-1,-0.5 \right)$} ;
\draw (-1.5,-1.5) node {$\bullet$};
\draw (-1.5,-1.5) node[below left] {$\left(-1.5,-1.5 \right)$} ;

\end{tikzpicture}
}
\end{center}
\end{figure}
\begin{figure}[h]
\begin{center}
\subfigure[Représentation de l'arbre kd] {
\begin{tikzpicture}[scale=1]

\tikzstyle{es}=[minimum width=2cm,ellipse,draw,rounded corners=4pt,fill=blue!25]
\tikzstyle{leaf}=[minimum width=2cm,rectangle,draw,fill=yellow!50]
\tikzstyle{axis}=[rectangle,draw,rounded corners=4pt,fill=red!50]

\node[es] (racine) at (0,0) {(-0.7,2) };
\node[es] (child1) at (-2.2,-2) {(-1,-0.5)};
\node[es] (child2) at ( 2.2,-2) {(0.7,1)};

\node[leaf] (leaf1) at ( -3.3,-4) {(-3,-1)};
\node[leaf] (leaf2) at ( -3.3,-4.6) {(-1.5,-1.5)};
\node[leaf] (leaf3) at ( -1.1,-4) {(-1,-0.5)};
\node[leaf] (leaf4) at ( -1.1,-4.6) {(-1.7,0.8)};
\node[leaf] (leaf5) at ( -1.1,-5.2) {(-3,1.5)};
\node[leaf] (leaf6) at (  1.1,-4) { (1.5,0) };
\node[leaf] (leaf7) at (  1.1,-4.6) { (2,-2) };
\node[leaf] (leaf8) at (  3.3,-4) { (0.7,1) };
\node[leaf] (leaf9) at (  3.3,-4.6) { (-0.7,2) };
\node[leaf] (leaf10) at (  3.3,-5.2) { (2,3) };

\node[axis] (axis1) at ( 6,0) {\Large{Ox}};
\node[axis] (axis1) at ( 6,-2) {\Large{Oy}};

\tikzstyle{suite}=[->,>=stealth,thick,rounded corners=4pt]
\draw[suite] (racine) -- (child1);
\draw[suite] (racine) -- (child2);
\draw[suite] (child1) -- (leaf1);
\draw[suite] (child1) -- (leaf3);
\draw[suite] (child2) -- (leaf6);
\draw[suite] (child2) -- (leaf8);

\draw[-,gray!100,dashed] (-5,-1) -- (6.5,-1);
\draw[-,gray!100,dashed] (-5,-3) -- (6.5,-3);
\end{tikzpicture}
}
\end{center}
\end{figure}

\subsection{Construction}
Il existe plusieurs possibilités de construction d'arbres kd, notament au niveau du choix des axes médians,
mais le principe reste le même. La direction de l'hyperplan est choisie en fonction de la hauteur du point. 
Pour un kd-tree en dimension 3, le plan de la racine sera par exemple normal au vecteur (1,0,0), le plan des 
deux enfants sera normal au vecteur (0,1,0), celui des petits-enfant sera normal au vecteur (0,0,1), 
puis à nouveau normal au vecteur (1,0,0), et ainsi de suite...

C'est un processus itératif, dont le critère d'arrêt est le nombre de point incluts dans chaque boites.
A partir d'un nuage de points, on se donne la direction d'un hyperplan. L'axe médian est alors le point 
qui divise en deux de manière équilibrées le nuage de point. (un ptit dessin). 

%Classiquement on utilise les hyperplans normaux à (1,0,0), (0,1,0) et (0,0,1)
Classiquement on utilise les vecteurs normaux (1,0,0), (0,1,0) et (0,0,1)

\subsection{Algorithme de recherche}
\begin{figure}[h]
\begin{center}
\subfigure[Organisation des points de l'espace] {
\begin{tikzpicture}[scale=8]
\draw (1,0.777778) node {$\bullet$};
\draw (1,0.888889) node {$\bullet$};
\draw (0.904673,0.838613) node {$\bullet$};
\draw (0.111111,0) node {$\bullet$};
\draw (0.222222,0) node {$\bullet$};
\draw (0.159258,0.0835926) node {$\bullet$};
\draw (0.115112,0.509481) node {$\bullet$};
\draw (0,0.555556) node {$\bullet$};
\draw (0,0.444444) node {$\bullet$};
\draw (0,0.333333) node {$\bullet$};
\draw (0.0821078,0.395349) node {$\bullet$};
\draw (0.0869427,0.153438) node {$\bullet$};
\draw (0.111769,0.286737) node {$\bullet$};
\draw (0,0.222222) node {$\bullet$};
\draw (0.746153,0.192955) node {$\bullet$};
\draw (0.77828,0.0876474) node {$\bullet$};
\draw (0.887425,0.176671) node {$\bullet$};
\draw (0.915464,0.296513) node {$\bullet$};
\draw (1,0.222222) node {$\bullet$};
\draw (1,0.333333) node {$\bullet$};
\draw (0.286767,0.100401) node {$\bullet$};
\draw (0.20422,0.182591) node {$\bullet$};
\draw (0.232032,0.298813) node {$\bullet$};
\draw (0.16565,0.913911) node {$\bullet$};
\draw (0.222222,1) node {$\bullet$};
\draw (0.111111,1) node {$\bullet$};
\draw (0,0.111111) node {$\bullet$};
\draw (1,0.111111) node {$\bullet$};
\draw (0.888889,1) node {$\bullet$};
\draw (0.777778,1) node {$\bullet$};
\draw (0.814339,0.8948) node {$\bullet$};
\draw (0.0977774,0.625081) node {$\bullet$};
\draw (0,0.666667) node {$\bullet$};
\draw (0.666667,0) node {$\bullet$};
\draw (0.777778,0) node {$\bullet$};
\draw (0.333333,0) node {$\bullet$};
\draw (0.470611,0.689362) node {$\bullet$};
\draw (0.561588,0.662591) node {$\bullet$};
\draw (0.542168,0.777929) node {$\bullet$};
\draw (0.601948,0.491358) node {$\bullet$};
\draw (0.571002,0.351378) node {$\bullet$};
\draw (0.673528,0.37938) node {$\bullet$};
\draw (0.724123,0.496955) node {$\bullet$};
\draw (0.495183,0.432796) node {$\bullet$};
\draw (0.408803,0.492829) node {$\bullet$};
\draw (0.413429,0.375595) node {$\bullet$};
\draw (0.396452,0.610624) node {$\bullet$};
\draw (0.501723,0.566162) node {$\bullet$};
\draw (0.362525,0.722667) node {$\bullet$};
\draw (0.553912,0.239603) node {$\bullet$};
\draw (0.490464,0.310022) node {$\bullet$};
\draw (0.412583,0.26242) node {$\bullet$};
\draw (0.472507,0.0918464) node {$\bullet$};
\draw (0.444444,0) node {$\bullet$};
\draw (0.555556,0) node {$\bullet$};
\draw (0.554339,0.138807) node {$\bullet$};
\draw (0.43203,0.804939) node {$\bullet$};
\draw (0.482552,0.1972) node {$\bullet$};
\draw (0.395586,0.155615) node {$\bullet$};
\draw (0.670634,0.610482) node {$\bullet$};
\draw (0.312296,0.21738) node {$\bullet$};
\draw (0.308581,0.54456) node {$\bullet$};
\draw (0.325713,0.433455) node {$\bullet$};
\draw (0.232693,0.485617) node {$\bullet$};
\draw (0.258713,0.392781) node {$\bullet$};
\draw (0.818177,0.474988) node {$\bullet$};
\draw (0.847807,0.375685) node {$\bullet$};
\draw (0.912012,0.487463) node {$\bullet$};
\draw (0.274491,0.656814) node {$\bullet$};
\draw (0.326046,0.324602) node {$\bullet$};
\draw (0.170415,0.698767) node {$\bullet$};
\draw (0.199986,0.589552) node {$\bullet$};
\draw (0.24456,0.754847) node {$\bullet$};
\draw (0.122156,0.816068) node {$\bullet$};
\draw (0.762322,0.408893) node {$\bullet$};
\draw (0.747973,0.317454) node {$\bullet$};
\draw (0.935056,0.387488) node {$\bullet$};
\draw (1,0.444444) node {$\bullet$};
\draw (1,0.555556) node {$\bullet$};
\draw (1,0.666667) node {$\bullet$};
\draw (0.887634,0.623865) node {$\bullet$};
\draw (0.386528,0.0695725) node {$\bullet$};
\draw (0.827633,0.270691) node {$\bullet$};
\draw (0.656259,0.109747) node {$\bullet$};
\draw (0.172071,0.394796) node {$\bullet$};
\draw (0.643309,0.247046) node {$\bullet$};
\draw (0.0714623,0.0696283) node {$\bullet$};
\draw (0,0) node {$\bullet$};
\draw (0.0793621,0.921875) node {$\bullet$};
\draw (0,1) node {$\bullet$};
\draw (0,0.888889) node {$\bullet$};
\draw (0.933541,0.926956) node {$\bullet$};
\draw (1,1) node {$\bullet$};
\draw (0.318301,0.82826) node {$\bullet$};
\draw (0.492441,0.891162) node {$\bullet$};
\draw (0.555556,1) node {$\bullet$};
\draw (0.444444,1) node {$\bullet$};
\draw (0.791872,0.570655) node {$\bullet$};
\draw (0.216106,0.842017) node {$\bullet$};
\draw (0,0.777778) node {$\bullet$};
\draw (0.380734,0.906064) node {$\bullet$};
\draw (0.577591,0.878332) node {$\bullet$};
\draw (0.621247,0.813568) node {$\bullet$};
\draw (0.676545,0.909001) node {$\bullet$};
\draw (0.643397,0.734697) node {$\bullet$};
\draw (0.584406,0.582605) node {$\bullet$};
\draw (0.0780697,0.716872) node {$\bullet$};
\draw (0.272724,0.915042) node {$\bullet$};
\draw (0.333333,1) node {$\bullet$};
\draw (0.666667,1) node {$\bullet$};
\draw (0.720393,0.804358) node {$\bullet$};
\draw (0.76957,0.697811) node {$\bullet$};
\draw (0.893405,0.731567) node {$\bullet$};
\draw (0.820476,0.79343) node {$\bullet$};
\draw (0.888729,0.0625715) node {$\bullet$};
\draw (1,0) node {$\bullet$};
\draw (0.888889,0) node {$\bullet$};
\draw[-,gray!100,dashed] (0.493812,0) -- (0.493812,1);
\draw[-,gray!100,dashed] (0.495183,0.515272) -- (1,0.515272);
\draw[-,gray!100,dashed] (0.76957,0.555556) -- (0.76957,1);
\draw[-,gray!100,dashed] (0.777778,0.79343) -- (1,0.79343);
\draw[-,gray!100,dashed] (0.542168,0.734697) -- (0.76957,0.734697);
\draw[-,gray!100,dashed] (0.777778,0) -- (0.777778,0.491358);
\draw[-,gray!100,dashed] (0.77828,0.222222) -- (1,0.222222);
\draw[-,gray!100,dashed] (0.495183,0.239603) -- (0.777778,0.239603);
\draw[-,gray!100,dashed] (0,0.58309) -- (0.490464,0.58309);
\draw[-,gray!100,dashed] (0.216106,0.610624) -- (0.216106,1);
\draw[-,gray!100,dashed] (0.222222,0.804939) -- (0.492441,0.804939);
\draw[-,gray!100,dashed] (0,0.777778) -- (0.216106,0.777778);
\draw[-,gray!100,dashed] (0.232032,0) -- (0.232032,0.555556);
\draw[-,gray!100,dashed] (0.232693,0.21738) -- (0.490464,0.21738);
\draw[-,gray!100,dashed] (0.325713,0.26242) -- (0.325713,0.54456);
\draw[-,gray!100,dashed] (0,0.182591) -- (0.222222,0.182591);
\draw[-,gray!100,dashed] (0,0.222222) -- (0,0.509481);
\end{tikzpicture}
}
\end{center}
\end{figure}

\newpage
\subsection{3DDD}


\tikzset{math3d/.style= {x= {(-0.353cm,-0.353cm)}, z={(0cm,1cm)},y={(1cm,0cm)}}}
%\begin{figure}[h]
%\begin{center}
%\subfigure[Organisation des points de l'espace] {
%\begin{tikzpicture}[scale=8,math3d]
%\tikzset{math3d/.style= {x= {(-0.353cm,-0.353cm)}, z={(0cm,1cm)},y={(1cm,0cm)}}}
\begin{figure}[h]
\begin{center}
\subfigure[Organisation des points de l'espace] {
\begin{tikzpicture}[scale=8]
\draw (0.767214,0,0.482292) node {$\bullet$};
\draw (0.423487,0.335588,0.588613) node {$\bullet$};
\draw (0.409583,0,0.625895) node {$\bullet$};
\draw (0.764413,0.335588,0.588613) node {$\bullet$};
\draw (0.764413,0.676512,0.588613) node {$\bullet$};
\draw (1,0.759097,0.779374) node {$\bullet$};
\draw (1,1,0.666667) node {$\bullet$};
\draw (0.774836,1,0.66092) node {$\bullet$};
\draw (0,0,1) node {$\bullet$};
\draw (0.333333,0,1) node {$\bullet$};
\draw (0.18066,0,0.827949) node {$\bullet$};
\draw (0.229395,0.325591,1) node {$\bullet$};
\draw (0,0.434805,0.660673) node {$\bullet$};
\draw (0,0.666667,1) node {$\bullet$};
\draw (0,0.333333,1) node {$\bullet$};
\draw (0,0.604279,0.310685) node {$\bullet$};
\draw (0,0.229717,0.325764) node {$\bullet$};
\draw (0,0.333333,0) node {$\bullet$};
\draw (0.229395,0.325591,0) node {$\bullet$};
\draw (0.817516,0.16088,0) node {$\bullet$};
\draw (1,0.333333,0) node {$\bullet$};
\draw (1,0.22308,0.204951) node {$\bullet$};
\draw (1,0,0) node {$\bullet$};
\draw (0.423487,0.676512,0.588613) node {$\bullet$};
\draw (0.423487,0.676512,0.247688) node {$\bullet$};
\draw (0.764413,0.676512,0.247688) node {$\bullet$};
\draw (0.604279,1,0.310685) node {$\bullet$};
\draw (0.423487,0.335588,0.247688) node {$\bullet$};
\draw (0.769852,0.658249,1) node {$\bullet$};
\draw (0.603399,0.310189,1) node {$\bullet$};
\draw (0.764413,0.335588,0.247688) node {$\bullet$};
\draw (0,0.817736,0.161005) node {$\bullet$};
\draw (0.182237,0.837882,0) node {$\bullet$};
\draw (0,0.666667,0) node {$\bullet$};
\draw (0,1,0) node {$\bullet$};
\draw (0.696133,0,0.795809) node {$\bullet$};
\draw (0.434805,1,0.660673) node {$\bullet$};
\draw (0.666667,1,1) node {$\bullet$};
\draw (0.395616,0.684861,1) node {$\bullet$};
\draw (1,0.472948,0.734999) node {$\bullet$};
\draw (0.817516,0.16088,1) node {$\bullet$};
\draw (1,0.333333,1) node {$\bullet$};
\draw (1,0.214413,0.761815) node {$\bullet$};
\draw (1,0,0.333333) node {$\bullet$};
\draw (1,0.496093,0.215224) node {$\bullet$};
\draw (1,0.690581,0.481814) node {$\bullet$};
\draw (1,0.285974,0.476198) node {$\bullet$};
\draw (0.666667,1,0) node {$\bullet$};
\draw (0.395616,0.684861,0) node {$\bullet$};
\draw (0.769852,0.658249,0) node {$\bullet$};
\draw (0,0.774836,0.66092) node {$\bullet$};
\draw (0.182237,0.837882,1) node {$\bullet$};
\draw (0,1,1) node {$\bullet$};
\draw (0.558858,0,0.236092) node {$\bullet$};
\draw (0,1,0.333333) node {$\bullet$};
\draw (0.229717,1,0.325764) node {$\bullet$};
\draw (1,1,1) node {$\bullet$};
\draw (1,0.770668,0.206074) node {$\bullet$};
\draw (0,0,0.666667) node {$\bullet$};
\draw (0.224691,0,0.303924) node {$\bullet$};
\draw (0.801507,0,0.198434) node {$\bullet$};
\draw (0.333333,1,0) node {$\bullet$};
\draw (0.666667,0,0) node {$\bullet$};
\draw (1,0,0.666667) node {$\bullet$};
\draw (1,0.666667,1) node {$\bullet$};
\draw (1,0.666667,0) node {$\bullet$};
\draw (0.333333,1,1) node {$\bullet$};
\draw (0,1,0.666667) node {$\bullet$};
\draw (0.603399,0.310189,0) node {$\bullet$};
\draw (0.817736,1,0.161005) node {$\bullet$};
\draw (0.333333,0,0) node {$\bullet$};
\draw (0,0,0) node {$\bullet$};
\draw (1,1,0.333333) node {$\bullet$};
\draw (0,0,0.333333) node {$\bullet$};
\draw (1,1,0) node {$\bullet$};
\draw (0.666667,0,1) node {$\bullet$};
\draw (1,0,1) node {$\bullet$};
\draw (0.764413,0.676512,0.588613) node {$\bullet$};
\draw (0.423487,0.676512,0.588613) node {$\bullet$};
\draw (0.423487,0.676512,0.247688) node {$\bullet$};
\draw (0.423487,0.335588,0.588613) node {$\bullet$};
\draw (0.423487,0.335588,0.247688) node {$\bullet$};
\draw (0.764413,0.676512,0.247688) node {$\bullet$};
\draw (0.764413,0.335588,0.588613) node {$\bullet$};
\draw (0.849644,0.591281,0.162456) node {$\bullet$};
\draw (0.764413,0.335588,0.247688) node {$\bullet$};
\draw[-,gray!100,fill=gray!20,opacity=0.5] (0.603399,0,0) -- (0.603399,0,1) -- (0.603399,1,1) -- (0.603399,1,0) -- (0.603399,0,0);
\draw[-,gray!100,fill=gray!20,opacity=0.5] (0.604279,0.472948,0) -- (0.604279,0.472948,1) -- (1,0.472948,1) -- (1,0.472948,0) -- (0.604279,0.472948,0);
\draw[-,gray!100,fill=gray!20,opacity=0.5] (0.604279,0.496093,0.310685) -- (0.604279,1,0.310685) -- (1,1,0.310685) -- (1,0.496093,0.310685) -- (0.604279,0.496093,0.310685);
\draw[-,gray!100,fill=gray!20,opacity=0.5] (0.774836,0.658249,0.333333) -- (0.774836,0.658249,1) -- (0.774836,1,1) -- (0.774836,1,0.333333) -- (0.774836,0.658249,0.333333);
\draw[-,gray!100,fill=gray!20,opacity=0.5] (0.769852,0.496093,0) -- (0.769852,0.496093,0.310685) -- (0.769852,1,0.310685) -- (0.769852,1,0) -- (0.769852,0.496093,0);
\draw[-,gray!100,fill=gray!20,opacity=0.5] (0.666667,0,0.476198) -- (0.666667,0.335588,0.476198) -- (1,0.335588,0.476198) -- (1,0,0.476198) -- (0.666667,0,0.476198);
\draw[-,gray!100,fill=gray!20,opacity=0.5] (0.767214,0,0.482292) -- (0.767214,0,1) -- (0.767214,0.472948,1) -- (0.767214,0.472948,0.482292) -- (0.767214,0,0.482292);
\draw[-,gray!100,fill=gray!20,opacity=0.5] (0.817516,0,0) -- (0.817516,0,0.476198) -- (0.817516,0.335588,0.476198) -- (0.817516,0.335588,0) -- (0.817516,0,0);
\draw[-,gray!100,fill=gray!20,opacity=0.5] (0,0.335588,0) -- (0,0.335588,1) -- (0.558858,0.335588,1) -- (0.558858,0.335588,0) -- (0,0.335588,0);
\draw[-,gray!100,fill=gray!20,opacity=0.5] (0,0.604279,0.333333) -- (0,1,0.333333) -- (0.434805,1,0.333333) -- (0.434805,0.604279,0.333333) -- (0,0.604279,0.333333);
\draw[-,gray!100,fill=gray!20,opacity=0.5] (0,0.434805,0.588613) -- (0,0.434805,1) -- (0,1,1) -- (0,1,0.588613) -- (0,0.434805,0.588613);
\draw[-,gray!100,fill=gray!20,opacity=0.5] (0,0.604279,0) -- (0,0.604279,0.333333) -- (0,1,0.333333) -- (0,1,0) -- (0,0.604279,0);
\draw[-,gray!100,fill=gray!20,opacity=0.5] (0,0,0.325764) -- (0,0.335588,0.325764) -- (0.603399,0.335588,0.325764) -- (0.603399,0,0.325764) -- (0,0,0.325764);
\draw[-,gray!100,fill=gray!20,opacity=0.5] (0.18066,0,0.333333) -- (0.18066,0,1) -- (0.18066,0.335588,1) -- (0.18066,0.335588,0.333333) -- (0.18066,0,0.333333);
\draw[-,gray!100,fill=gray!20,opacity=0.5] (0.229395,0,0) -- (0.229395,0,0.325764) -- (0.229395,0.335588,0.325764) -- (0.229395,0.335588,0) -- (0.229395,0,0);

\end{tikzpicture}
}
\end{center}
\end{figure}


\section{Tests Numériques}

\subsection{Convergence h/p}
Soit $u\in Xh_{\Omega_{1}}$. Cette fonction est calculée par une projection $H^{1}$ à partir d'une fonction analytique,
comme par exemple :
\begin{equation}
sol\left(x,y\right) = \cos\left( \frac{\pi x}{2} \right) \cos\left( \frac{\pi y}{2} \right)
\end{equation}

\paragraph{}
Estimations d'erreur :

\begin{equation}
\| u-\pi\left(u\right) \| \leq C h^{\mu-1} P^{-\left(k-1\right)} \|u\|
\end{equation}



\begin{figure}[H]
\centering
\includegraphics[scale=0.35]{conv_hp2}
\end{figure} 




\subsection{Décomposition de domaine}



\end{document}